package cn.bouncyslime.algorithms.sort.insertSort;

public class HalfSort2 {
	public static void main(String[] args) {
		int low,high,mid=0;
		int demo;
		int[] array = {11,13,2,34,55,9,44,122,32,2,9};
//		int[] array = {1,2,3,4,5};
		int flag = 0;
		int flag2 = 0;
		//从头开始遍历数组，将array[i+1]插入到从头开始的已排好序的队列中的正确的位置中去
		for(int i=0; i<array.length-1; i++) {
			//做出判断，交换位置
			low = 0;
			high = i;
			demo = array[i+1];
			while(low <= high) {
				mid = (low+high)/2;
				if(demo < array[mid]) {
					//当要查找的数比中小时
					high = mid - 1;
					flag ++;
				}else if(demo >= array[mid]) {
					//当要查找的数比中大时
					low = mid + 1;
					flag ++;
				}
			}
			for(int j=i; j>=low; j--) {
				array[j+1] = array[j];
				flag2 ++;
			}
			array[low] = demo;
			for(int m=0; m<array.length; m++) {
				System.out.printf("%d ",array[m]);
			}
			System.out.println();
		}	
		
		System.out.println("以下为最终答案！");
		System.out.println("进行了"+flag+"次比较！");
		System.out.println("进行了"+flag2+"次移动！");
		for(int m=0; m<array.length; m++) {
			System.out.printf("%d ",array[m]);
		}
	}
}
